import numpy as np
import random as rd
def ER1(n, m):#固定边数ER随机图
    G = np.empty((n, n))
    lst = []
    for i in range(0, n):
        G[i][i] = -1
        for j in range(i + 1, n):
            G[i][j] = G[j][i] = -1
            lst.append([i, j])
            lst.append([j, i])
    tmp_m = 0
    while(tmp_m > 0):
        k = rd.randint(0, tmp_m)
        tmp_ls = lst[k]
        G[tmp_ls[0]][tmp_ls[1]] = 1
        G[tmp_ls[1]][tmp_ls[0]] = 1
        lst.remove([tmp_ls[0], tmp_ls[1]])
        lst.remove([tmp_ls[1], tmp_ls[0]])
        tmp_m -= 2
    return G

def ER2(n, p):#固定连边概率ER随机图
    G = np.empty((n, n))
    for i in range(0, n):
        G[i][i] = -1
        for j in range(i + 1, n):
            G[i][j] = G[j][i] = -1
            r = rd.random()
            if(r < p):
                G[i][j] = G[j][i] = 1
    return G
            
def WS(n, k, p):#WS小世界
    G = np.empty((n, n))
    lst = []
    for i in range(0, n):
        G[i][i] = -1
        for j in range(i + 1, n):
            G[i][j] = G[j][i] = -1

    for i in range(0, n):
        for j in range(0, k / 2):
            nxt = (i + j + 1) % n 
            G[i][nxt] = G[nxt][i] = 1
            lst.append([nxt, i])
            lst.append([i, nxt])
    tmp_m = len(lst)
    while(tmp_m > 0):
        k = rd.randint(0, tmp_m)
        r = rd.random()
        tmp_ls = lst[k]
        if(r < p):
            cp_lst = []
            for i in range(0, n):
                if(i != tmp_ls[0] and G[tmp_ls[0]][i] == -1):
                    cp_lst.append(i)
            if(len(cp_lst) == 0):
                lst.remove([tmp_ls[0], tmp_ls[1]])
                lst.remove([tmp_ls[1], tmp_ls[0]])
                tmp_m -= 2
                continue
            rdp = rd.choice(cp_lst)
            G[tmp_ls[0]][tmp_ls[1]] = -1
            G[tmp_ls[1]][tmp_ls[0]] = -1
            G[tmp_ls[0]][rdp] = 1
            G[rdp][tmp_ls[0]] = 1
        
        lst.remove([tmp_ls[0], tmp_ls[1]])
        lst.remove([tmp_ls[1], tmp_ls[0]])
        tmp_m -= 2
    return G
    
def NW(n, k, p):#NW小世界
    G = np.empty((n, n))
    for i in range(0, n):
        G[i][i] = -1
        for j in range(i + 1, n):
            G[i][j] = G[j][i] = -1

    for i in range(0, n):
        for j in range(0, k / 2):
            nxt = (i + j + 1) % n 
            G[i][nxt] = G[nxt][i] = 1
    cnt = n * k / 2
    while(cnt > 0):
        cnt -= 1
        r = rd.random()
        if(r >= p):
            continue
        while(True):
            u = rd.randint(0, n)
            v = rd.randint(0, n)
            if(u != v and G[u][v] == -1 and G[v][u] == -1):
                G[u][v] = G[v][u] = 1
                break
    return G

def BA(n, m0, m):#无标度网络
    G = np.empty((n, n))
    deg = np.zeros((n))
    for i in range(1, m0):
        G[i - 1][i] = G[i][i - 1] = 1
        deg[i] += 1
        deg[i - 1] += 1
    for i in range(m0, n):
        cnt = 0
        prep = vis = np.zeros((n))
        p = deg 
        sump = np.sum(p)
        p = p / sump#优先连接
        prep[0] = 0
        for j in range(1, n):
            prep[i] = prep[i - 1] + p[i]
        while(cnt < m):#连m条边
            r = rd.random()
            for j in range(1, n):
                if(r > prep[j]):
                    if(vis[j - 1] == 0):
                        G[i][j - 1] = G[j - 1][i] = 1
                        vis[j - 1] = 1
                        cnt += 1
                        break
        deg[i] = m
        deg = deg + vis#更新入度
    return G

def Price(m0, n, a, m):#Price有向网络模型构造算法，m0个初始节点，最终n个节点，常数a，每次新节点连边数m
    G = np.empty((n, n))
    deg = np.zeros((n))#入度
    for i in range(m0, n):
        cnt = 0
        prep = vis = np.zeros((n))
        p = deg 
        sump = np.sum(p)
        p = p + a
        p = p / (sump + a * i)#累计优势
        prep[0] = 0
        for j in range(1, n):
            prep[i] = prep[i - 1] + p[i]
        while(cnt < m):#连m条边
            r = rd.random()
            for j in range(1, n):
                if(r > prep[j]):
                    if(vis[j - 1] == 0):
                        G[i][j - 1] = 1
                        vis[j - 1] = 1
                        cnt += 1
                        break
        for j in range(0, i):#更新入度
            deg[j] += vis[j]

def Big_Price(m0, n, p, m):#n足够大时的Price有向网络模型构造算法
    G = np.empty((n, n))
    arr = []#array数组
    for i in range(1, m0):
        G[i - 1][i] = G[i][i - 1] = 1
        arr.append(i - 1)
        arr.append(i)
    lst = [j for j in range(0, m0)]
    for i in range(m0, n):
        cnt = 0
        tmp_arr = arr
        tmp_lst = lst
        go = []
        while(cnt < m):#连m条边
            cnt += 1
            r = rd.random()
            if(r < p):
                rp = rd.choice(tmp_arr)
            else:
                rp = rd.choice(tmp_lst)
            arr.append(rp)
            G[i][rp] = 1
            cnt_rp = tmp_arr.count(rp)
            for j in range(0, cnt_rp):
                tmp_arr.remove(rp)
            tmp_lst.remove(rp)
        lst.append(i)

    return G

def Copy_Point(m0, n, p, m):#节点复制模型
    G = np.empty((n, n))
    arr = []#array数组
    lst = [j for j in range(0, m0)]
    for i in range(m0, n):
        cnt = 0
        tmp_arr = arr
        tmp_lst = lst
        go = []
        while(cnt < m):#连m条边
            cnt += 1
            r = rd.random()
            _rp = -1
            if(r < p):
                rp = rd.choice(tmp_arr)
                if(cnt < m):
                    cnt += 1
                    neb = []
                    for j in tmp_lst:
                        if(G[rp][j] == 1):
                            neb.append(j)
                    _rp = rd.choice(neb)
            else:
                rp = rd.choice(tmp_lst)
            arr.append(rp)
            G[i][rp] = 1
            cnt_rp = tmp_arr.count(rp)
            for j in range(0, cnt_rp):
                tmp_arr.remove(rp)
            if(_rp != -1):
                arr.append(_rp)
                G[i][_rp] = 1
                _cnt_rp = tmp_arr.count(_rp)
                for j in range(0, _cnt_rp):
                    tmp_arr.remove(_rp)
            tmp_lst.remove(rp)
        lst.append(i)
    return G

def Ada(m0, n, eta, m):#适应度模型
    G = np.empty((n, n))
    deg = np.zeros((n))
    for i in range(1, m0):
        G[i - 1][i] = G[i][i - 1] = 1
        deg[i] += 1
        deg[i - 1] += 1
    for i in range(m0, n):
        cnt = 0
        prep = vis = np.zeros((n))
        p = deg * eta
        sump = np.sum(p)
        p = p / sump#优先连接
        prep[0] = 0
        for j in range(1, n):
            prep[i] = prep[i - 1] + p[i]
        while(cnt < m):#连m条边
            r = rd.random()
            for j in range(1, n):
                if(r > prep[j]):
                    if(vis[j - 1] == 0):
                        G[i][j - 1] = G[j - 1][i] = 1
                        vis[j - 1] = 1
                        cnt += 1
                        break
        deg[i] = m
        deg = deg + vis#更新度
    return G

def Local_World(m0, e0, n, m, M):#局域世界
    G = np.empty((n, n))
    _G = ER1(m0, e0)
    deg = np.zeros((n))
    for i in range(0, m0):
        G[i] = _G[i]
        deg[i] = np.sum(G)
    for i in range(m0, n):
        lw = rd.sample(range(i), k = M)
        sump = 0
        for j in lw:
            sump += deg[j]
        cnt = 0
        prep = vis = np.zeros((n))
        p = deg
        p = (M * p) / ((i + 1) * sump)#优先连接
        prep[0] = 0
        for j in range(1, n):
            prep[i] = prep[i - 1] + p[i]
        while(cnt < m):#连m条边
            r = rd.random()
            for j in range(1, n):
                if(r > prep[j]):
                    if(vis[j - 1] == 0):
                        G[i][j - 1] = G[j - 1][i] = 1
                        vis[j - 1] = 1
                        cnt += 1
                        break
        deg[i] = m
        deg = deg + vis#更新度
    return G